package string;

import java.util.Stack;

/**
 * 917.Reverse Only Letters 仅仅反转字母
 *
 Given a string S, return the "reversed" string
 where all characters that are not a letter stay in the same place,
 and all letters reverse their positions.

 Example 1:

 Input: "ab-cd"
 Output: "dc-ba"
 Example 2:

 Input: "a-bC-dEf-ghIj"
 Output: "j-Ih-gfE-dCba"
 Example 3:

 Input: "Test1ng-Leet=code-Q!"
 Output: "Qedo1ct-eeLg=ntse-T!"

 Note:

 S.length <= 100
 33 <= S[i].ASCIIcode <= 122
 S doesn't contain \ or "
 */
public class Q917_ReverseOnlyLetters {

    /**
     * double pointer
     */
    private String reverseOnlyLetters(String S) {
        int stat = 0;
        int end = S.length()-1;
        char[] chs = S.toCharArray();
        while (stat < end) {
            while (stat<end && !((chs[stat]>='A' && chs[stat]<='Z') || (chs[stat]>='a' && chs[stat]<='z'))) {
                stat++;
            }
            while (end>stat && !((chs[end]>='A' && chs[end]<='Z') || (chs[end]>='a' && chs[end]<='z'))) {
                end--;
            }
            if (stat < end) {
                swap(chs, stat, end);
            }
            stat++;
            end--;
        }
        return String.valueOf(chs);
    }

    private void swap(char[] chs, int i, int j) {
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }

    /**
     * stat index aims to find a character that is not a letter
     * end index aims to find a letter
     */
    private String reverseOnlyLetters1(String S) {
        StringBuilder ans = new StringBuilder();
        int end = S.length()-1;
        for (int stat=0; stat<S.length(); stat++) {
            if (Character.isLetter(S.charAt(stat))) {
                while (!Character.isLetter(S.charAt(end))) {
                    end--;
                }
                ans.append(S.charAt(end--));
            } else {
                //keep non-letter's position is not changed
                ans.append(S.charAt(stat));
            }
        }
        return ans.toString();
    }

    /**
     * Stack
     */
    private String reverseOnlyLettersStack(String s) {
        Stack<Character> s1 = new Stack<>();
        for (Character ch: s.toCharArray()) {
            if (Character.isLetter(ch)) {
                s1.add(ch);
            }
        }
        StringBuilder ans = new StringBuilder();
        for (Character ch: s.toCharArray()) {
            if (Character.isLetter(ch)) {
                ans.append(s1.pop());
            } else {
                ans.append(ch);
            }
        }
        return ans.toString();
    }

    public static void main(String[] args) {
        Q917_ReverseOnlyLetters q917_reverseOnlyLetters = new Q917_ReverseOnlyLetters();
        String res = q917_reverseOnlyLetters.reverseOnlyLetters("--");
        System.out.println(res);
    }

}
